package lib

import "sort"

//link to 
func init() {
	Probs = append(Probs, Problem{
		Num:         923,
		Discription: "仅要求下标递增的三数之和",
		Level:       2,
		Labels: map[string]int{
			"排序":   1,
			"双指针滑动": 1,
			"去重": 1,
		},
	})
}

func ThreeSumMulti(arr []int, target int) int {
	sort.Ints(arr)
	n := len(arr)
	res := 0
	for i := 0; i <= n-3; i++ {
		left := i + 1
		right := n - 1
		for left < right {
			sum := arr[i] + arr[left] + arr[right]
			//区别在这：有重复数组的情况
			if sum == target {
				//头尾都一样：组合数=1+2+...+n
				if arr[left] == arr[right] {
					res += (right - left) * (right - left + 1) / 2
					break
				}

				//头尾各自有一部分一样：组合数=左边一样的数量*右边一样的数量
				leftCount := 1
				for left < right && arr[left] == arr[left+1] {
					leftCount++
					left++
				}
				rightCount := 1
				for left < right && arr[right] == arr[right-1] {
					right--
					rightCount++
				}
				res += leftCount * rightCount
				left++
			} else if sum > target {
				right--
			} else {
				left++
			}
		}
	}

	return res % (1e9 + 7)
}